#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int mySqrt(int x) {
        int left = 0; int right = x;
        int mid;
        int ans = -1;
        while(left<=right){
            mid = (left+right)>>1;
            long long squart_x = (long long)mid*mid;
            if(squart_x <= x){
                ans = mid;
                left = mid+1;
            }
            else if(squart_x > x) right = mid - 1;
        }
        return ans;
    }
};